<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>数据结构之队列</title>
  </head>
  <body>
    <script type="text/javascript">
      function Queue() {
        this.dataStore = [];
        this.enqueue = enqueue; // 入队
        this.dequeue = dequeue; // 出队
        this.head = head; // 获取队首元素
        this.tail = tail; // 获取队尾元素
        this.length = length; // 获取队列长度
        this.toString = toString; // 显示队列中的所有元素
        this.isEmpty = isEmpty; // 判断队列是否为空
      }

      function enqueue(element) {
        this.dataStore.push(element);
      }

      function dequeue() {
        return this.dataStore.shift();
      }

      function head() {
        return this.dataStore[0];
      }

      function tail() {
        return this.dataStore[this.dataStore.length - 1];
      }

      function length() {
        return this.dataStore.length;
      }

      function isEmpty() {
        return this.dataStore.length === 0;
      }

      function toString() {
        var str = "";
        for (var i = 0; i < this.dataStore.length; i++) {
          str += this.dataStore[i] + "\n";
        }
        return str;
      }

      // var queue = new Queue();
      // queue.enqueue(1);
      // queue.enqueue(2);
      // console.log(queue.toString());
      // queue.dequeue();
      // console.log(queue.toString());

      // 模拟伤的更重的病人先得到救治
      // function Patient(name, code) {
      //   this.name = name;
      //   this.code = code;
      // }
      // 重写出队方法
      // function dequeue() {
      //   var priority = 0;
      //   for (var i = 1; i < this.dataStore.length; i++) {
      //     if (this.dataStore[i].code > this.dataStore[priority].code) {
      //       priority = i;
      //     }
      //   }
      //   return this.dataStore.splice(priority, 1);
      // }
      // // 重写显示整个队列的方法
      // function toString() {
      //   var str = '';
      //   for (var i = 0; i < this.dataStore.length; i++) {
      //     str += this.dataStore[i].name + ' code:' + this.dataStore[i].code + '\n';
      //   }
      //   return str;
      // }

      // var p = new Patient('小白', 2);
      // var p1 = new Patient('小黑', 4);
      // var p2 = new Patient('小红', 1);
      // var p3 = new Patient('小黄', 5);
      // var queue = new Queue();
      // queue.enqueue(p);
      // queue.enqueue(p1);
      // queue.enqueue(p2);
      // queue.enqueue(p3);
      // console.log('第一个被救治的人是：', queue.dequeue()[0]);

      //用两个队列实现一个栈
      // function QueueStack() {
      //   var queue1 = new Queue();
      //   var queue2 = new Queue();
      //   var data_queue = new Queue(); //存放数据的队列
      //   var empty_queue = new Queue(); //空队列

      //   //初始化队列，用来改变data_queue和empty_queue的指向，让data_queue始终指向有数据的队列，empty_queue指向空队列
      //   var init_queue = function () {
      //     if (queue1.isEmpty() && queue2.isEmpty()) {
      //       data_queue = queue1;
      //       empty_queue = queue2;
      //     } else if (queue1.isEmpty()) {
      //       data_queue = queue2;
      //       empty_queue = queue1;
      //     } else {
      //       data_queue = queue1;
      //       empty_queue = queue2;
      //     }
      //   };

      //   this.push = function (item) {
      //     init_queue();
      //     data_queue.enqueue(item);
      //   };

      //   this.top = function () {
      //     init_queue();
      //     return data_queue.tail();
      //   };

      //   this.pop = function () {
      //     init_queue();
      //     while (data_queue.length() > 1) {
      //       empty_queue.enqueue(data_queue.dequeue());
      //     }
      //     return data_queue.dequeue();
      //   };
      // }
      // var qStack = new QueueStack();
      // qStack.push(1);
      // console.log(qStack.top());
      // qStack.push(2);
      // console.log(qStack.top());
      // qStack.push(3);
      // console.log(qStack.top());
      // qStack.pop();
      // console.log(qStack.pop());
      // console.log(qStack.top());

      // //约瑟夫环
      // function del_ring(arr_list) {
      //   var queue = new Queue();
      //   //将数组里的元素放入队列
      //   for (var i = 0; i < arr_list.length; i++) {
      //     queue.enqueue(arr_list[i]);
      //   }
      //   var index = 0;
      //   while (queue.length() != 1) {
      //     //弹出一个元素，判断是否需要删除
      //     var item = queue.dequeue();
      //     index += 1;
      //     // 每隔两个就要删除掉⼀一个,那么不不是被删除的元素就放回到队列列尾部
      //     if (index % 3 != 0) {
      //       queue.enqueue(item);
      //     }
      //   }
      //   return queue.head();
      // }
      // var arr_list = [];
      // for (var i = 0; i < 100; i++) {
      //   arr_list.push(i);
      // }
      // console.log(del_ring(arr_list));

      //斐波那契序列
      // function fibonacci(n) {
      //   queue = new Queue();
      //   var index = 0;
      //   //先放入斐波那契序列的前两个数
      //   queue.enqueue(1);
      //   queue.enqueue(1);
      //   while (index < n - 2) {
      //     //出一个队列元素
      //     var del_item = queue.dequeue();
      //     //取队列头部元素
      //     var head_item = queue.head();
      //     var next_item = del_item + head_item;
      //     //将计算结果放入队列
      //     queue.enqueue(next_item);
      //     index += 1;
      //   }
      //   return queue.tail();
      // }
      // console.log(fibonacci(2));

      // 循环队列，实现击鼓传花
      // function drumming(names, number) {
      //   var queue = new Queue();
      //   for (var i = 0; i < names.length; i++) {
      //     queue.enqueue(names[i]);
      //   }
      //   while (queue.length() > 1) {
      //     for (var i = 0; i < number - 1; i++) {
      //       queue.enqueue(queue.dequeue());
      //     }
      //     var dieout = queue.dequeue();
      //     console.log("此轮被淘汰的玩家是：" + dieout);
      //   }
      //   console.log("游戏的最终赢家是：" + queue.dequeue());
      // }
      // // 玩家列表
      // var names = ["a", "b", "c", "d", "e", "f"];
      // // 游戏规则：从一名玩家开始传花，当传到第3次的时候，花在谁手里，谁就被淘汰，直到最后只剩一名玩家。
      // var number = 3;
      // drumming(names, number);

      // 优先队列：出列的时候跟普通队列一样，主要是入列的时候比较麻烦，要考虑到优先级的问题
      function PriorityQueue() {
        var items = [];

        // 辅助类
        var QueueItem = function (item, priority) {
          this.item = item; // 元素
          this.priority = priority; // 优先级
        };

        // 入列
        this.enqueue = function (item, priority) {
          var queueItem = new QueueItem(item, priority);
          var isAdd = false; // 判断是否插入成功
          for (var i = 0; i < items.length; i++) {
            if (queueItem.priority > items[i].priority) {
              // 遍历元素比较优先级
              items.splice(i, 0, queueItem); // 重点！从索引为i的位置开始切，切0个，并替换成queueItem。巧妙地使用splice这个函数实现了元素的插入
              isAdd = true;
              break;
            }
          }
          if (!isAdd) {
            // 貌似有点懂了
            items.push(queueItem);
          }
        };

        this.getItems = function () {
          return items;
        };
      }
      var pq = new PriorityQueue();
      pq.enqueue("小红", 12);
      pq.enqueue("小明", 10);
      pq.enqueue("小黑", 11);
      console.log(pq.getItems());
    </script>
  </body>
</html>
